/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-05-12
 * Time: 23:19
 * To BE A Better Person-2020-3-2
 */
//hh
class MyDoubleList{
        static class Node{
            public int val;
            public Node prev;
            public Node next;
            public Node(int val){
                this.val=val;
            }
        }
        public Node head;
        public Node last;
    //头插法
    public void addFirst(int data){
        Node node=new Node(data);
        if(head==null && last==null) {
            head = node;
            last = node;
        }else{
            head.prev=node;
            node.next=head;
            head=node;
        }
    }
    //尾插法
    public void addLast(int data){
        Node node=new Node(data);
        if(head==null && last==null) {
            head = node;
            last = node;
        }else{
            last.next=node;
            node.prev=last;
            last=node;
        }
    }
    private void JudgeIndex(int index) {
        if(index>size()-1||index<0){
            throw new RuntimeException("the index is out of bound");
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        JudgeIndex(index);
        Node node=new Node(data);
        Node cur=head;
        if(index == 0) {
            addFirst(data);
        }else if(index == (size()-1) ){
            addLast(data);
        }else{
            while (index!=1){
                cur=cur.next;
                index--;
            }
            cur.prev.next=node;
            node.prev=cur.next;
            node.next=cur;
            cur.prev=node;
        }

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while(cur != null) {
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(key == head.val) {
            Node node = head;
            node.next=null;
            node.prev=null;
            head = head.next;
            head.prev=null;
        }else if(key == last.val) {
            Node node = last;
            last = last.prev;
            node.prev=null;
            node.next=null;
            last.next=null;
        }else{
            Node cur = head;
            while(cur.val != key) {
                cur=cur.next;
            }
            cur.prev.next=cur.next;
            cur.next.prev=cur.prev;
            cur.next=null;
            cur.prev=null;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){

        //如果头节点就是key
        if(head.val == key){
           while(head.val == key){
               head=head.next;
               head.prev.next = null;
               head.prev=null;
           }
        }else{
            Node cur=this.head.next;
            Node prev=this.head;
            while(cur != null) {
                if(cur.val == key) {
                    prev.next=cur.next;
                    cur=cur.next;
                }else {
                    prev = cur;
                    cur = cur.next;
                }
            }
        }
    }
    //得到单链表的长度
    public int size(){
        int size=0;
        Node cur=head;
        while(cur!=null){
            size++;
            cur=cur.next;
        }
        return size;

    }
    public void display(){
        Node cur=head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
    public void clear(){

    }
}
public class TestDemo {
    public static void main(String[] args) {
        MyDoubleList myDoubleList=new MyDoubleList();
        myDoubleList.addFirst(1);
        myDoubleList.addFirst(2);
        myDoubleList.addFirst(3);
        myDoubleList.addFirst(4);
        myDoubleList.addFirst(5);
        myDoubleList.display();
        System.out.println();
        System.out.println("==============");
        myDoubleList.addLast(99);
        myDoubleList.addLast(98);
        myDoubleList.addLast(97);
        myDoubleList.addLast(96);
        myDoubleList.addLast(95);
        myDoubleList.display();
        System.out.println();
        System.out.println(myDoubleList.size());
        System.out.println();
        System.out.println("==============");
        System.out.println();
        myDoubleList.addIndex(2,23);
        myDoubleList.display();
        myDoubleList.remove(99);
        System.out.println();
        myDoubleList.display();
        System.out.println();
        System.out.println("==============");
        myDoubleList.addLast(2);
        myDoubleList.display();
        System.out.println();
        myDoubleList.removeAllKey(2);
        System.out.println();
    }
}
